\subsection{Hamiltonian graphs}
\begin{definition}
	A graph is said to be \emph{Hamiltonian} if it contains a cycle that contains all vertices.
	Such a cycle is called a \emph{Hamilton cycle}.
\end{definition}
\begin{theorem}
	Let \( G \) be a graph on \( n \geq 3 \) vertices.
	Then if \( \delta(G) \geq \frac{n}{2} \), \( G \) is Hamiltonian.
\end{theorem}
\begin{remark}
	This theorem is sharp.
	If \( n \) is even, two disjoint \( K_{\frac{n}{2}} \) cliques suffices for a counterexample, since \( \delta(G) = \frac{n}{2} - 1 \).
	If \( n \) is odd, we can take two \( K_{\frac{n+1}{2}} \) cliques which intersect in a single vertex, giving \( \delta(G) = \frac{n-1}{2} \).
\end{remark}
\begin{proof}
	First, note that \( G \) is connected.
	Indeed, if \( x \not\sim y \), \( \abs{N(x)}, \abs{N(y)} \geq \frac{n}{2} \), but there are only \( n - 2 \) remaining vertices in the graph.
	So by the pigeonhole principle, there is a path of length 2 between \( x \) and \( y \).

	Consider a path \( x_1, \dots, x_\ell \) of maximum length, and suppose for a contradiction that there is no cycle in \( G \) of length \( \ell \).
	Observe that \( N(x_1) \subseteq \qty{x_2, \dots, x_{\ell - 1}} \) by maximality, and \( N(x_\ell) \subseteq \qty{x_2, \dots, x_{\ell - 1}} \) by symmetry.
	Define \( N^-(x_1) = \qty{x_i \mid x_{i+1} \in N(x_1)} \).
	Note that \( \abs{N^-(x_1) \cup N(x_\ell)} \leq \ell - 1 \leq n - 1 \), but \( \abs{N^-(x_1)}, \abs{N(x_\ell)} \geq \frac{n}{2} \).
	So there exists \( x_i \in N^-(x_1) \cap N(x_\ell) \).
	So we can find a cycle \( x_i, x_\ell, x_{\ell-1}, \dots, x_{i+1}, x_1, x_2, \dots, x_i \) of length \( \ell \).
\end{proof}
\begin{remark}
	Note that there is not an interesting theorem of the form `\( e(G) \geq k \) implies \( G \) is Hamiltonian', because \( K_{n-1} \) adjoined to a single vertex by one edge is not Hamiltonian.
\end{remark}

\subsection{Paths of a given length}
\begin{lemma}
	Let \( G \) be a graph on \( n \) vertices, and \( n \geq 3 \).
	Let \( k < n \).
	If \( G \) is connected and \( \delta(G) \geq \frac{k}{2} \), then \( G \) contains a path of length \( k \).
\end{lemma}
\begin{remark}
	We need the assumption \( k < n \), otherwise \( K_n \) is a counterexample.
	We need the assumption that \( G \) is connected, otherwise a collection of \( \frac{n}{k} \) disjoint graphs give a counterexample if \( n \mid k \).
	The requirement that \( \delta(G) \geq \frac{k}{2} \) is sharp, by considering collections of \( K_{\frac{k+1}{2}} \) that all intersect in a single vertex.
\end{remark}
\begin{proof}
	Let \( x_1, \dots, x_\ell \) be a path of maximum length in \( G \).
	There is no cycle of length \( \ell \), because if \( \ell = n \) we are done as \( k < n \), and if \( \ell < n \) we can use a cycle of length \( \ell \) to build a path of length \( \ell + 1 \) by the same argument from the previous theorem: \( N^-(x_1) \) and \( N(x_\ell) \) must intersect and so we can build a longer path.
\end{proof}
\begin{theorem}
	Let \( G \) be a graph on \( n \) vertices.
	Then if \( e(G) > \frac{n(k-1)}{2} \), \( G \) contains a path of length \( k \).
\end{theorem}
\begin{remark}
	If \( k \mid n \), a collection of \( \frac{n}{k} \) disjoint \( K_k \) graphs shows that the theorem is sharp.
\end{remark}
\begin{proof}
	Note that if \( k = 1 \), the theorem clearly holds.
	Suppose \( k \geq 2 \), and apply induction on \( n \).
	The case \( n = 2 \) holds vacuously.
	Suppose now we have a graph \( G \) on \( n \geq 3 \) vertices.
	First note that \( \frac{n(k-1)}{2} < e(G) \leq \frac{n(n-1)}{2} \), so \( k < n \).

	We may assume \( G \) is connected without loss of generality, because if it is disconnected, we can apply induction to one of its connected components.
	Let \( C_1, \dots, C_r \) be the components, and \( \abs{C_i} = n_i \).
	Since \( \sum_{i=1}^r e(G[C_i]) = e(G) > \frac{n(k-1)}{2} \), we have \( \sum_{i=1}^r \qty(e(G[C_i]) - \frac{n_i(k - 1)}{2}) > 0 \), so one of the summands is positive.
	So there exists a connected component \( C_i \) such that \( e(G[C_i]) > \frac{n_i(k-1)}{2} \), so we can apply induction to this graph to obtain a path of length \( k \) as required.

	If \( \delta(G) \geq \frac{k}{2} \), the proof is complete by the previous lemma.
	Otherwise, there exists a vertex \( x \) of degree less than \( \frac{k}{2} \), so \( \deg(x) \leq \frac{k-1}{2} \).
	Note that \( e(G - x) > \frac{n(k-1)}{2} - \frac{k-1}{2} = \frac{(n-1)(k-1)}{2} \), so we can apply induction to \( G - x \) to obtain a path of length \( k \), completing the proof.
\end{proof}

\subsection{Forcing triangles}
\begin{proposition}[Jensen]
	Let \( a < b \) be real numbers, and \( f \colon [a,b] \to \mathbb R \) be a convex function.
	Let \( x_1, \dots, x_n \in [a,b] \).
	Then, \( f\qty(\frac{1}{n}\sum_{i=1}^n x_i) \leq \frac{1}{n} \sum_{i=1}^n f(x_i) \).
\end{proposition}
\begin{theorem}[Mantel]
	Let \( G \) be a graph on \( n \) vertices, and \( \frac{n^2}{4} < e(G) \).
	Then \( G \) contains a triangle.
\end{theorem}
\begin{remark}
	The bipartite graph \( K_{\frac{n}{2}, \frac{n}{2}} \) contains no triangles, and has \( \frac{n^2}{4} \) edges, so the above theorem is sharp.
\end{remark}
\begin{proof}
	Suppose the graph contains no triangle.
	We may assume that \( n \geq 3 \), otherwise there is nothing to prove.
	Let \( x, y \in V(G) \) such that \( x \sim y \).
	In particular, \( \deg x + \deg y \leq n - 2 + 2 = n \).
	Then, since \( x \mapsto x^2 \) is convex,
	\begin{align*}
		n\cdot e(G) &\geq \sum_{x \sim y} (\deg x + \deg y) \\
		&= \frac{1}{2} \sum_x \sum_y (\deg x + \deg y) \symbb 1_{x \sim y} \\
		&= \sum_x \sum_y \deg x \symbb 1_{x \sim y} \\
		&= \sum_x \deg x \sum_y \symbb 1_{x \sim y} \\
		&= \sum_x (\deg x)^2 \\
		&= n \qty( \frac{1}{n} \sum_x (\deg x)^2 ) \\
		&\geq n \qty( \frac{1}{n} \sum_x (\deg x) )^2 \\
		&= n \qty( \frac{2e(G)}{n} )^2
	\end{align*}
	So \( e(G) \leq \frac{n^2}{4} \) as required.
\end{proof}

\subsection{Forcing cliques}
\begin{definition}
	We say that a graph \( G \) is \emph{\( r \)-partite} if there is a partition of \( V \) into \( r \) subsets such that no part contains an edge.
	Equivalently, \( G \) is \( r \)-colourable, so \( \chi(G) \leq r \).
\end{definition}
\begin{definition}
	Given natural numbers \( n_1, \dots, n_r \), define \( K_{n_1, \dots, n_r} \) to be the complete \( r \)-partite graph with partitions of size \( n_1, \dots, n_r \).
\end{definition}
Observe that if \( r \mid n \), the graph \( K_{\frac{n}{r}, \dots, \frac{n}{r}} \) is an \( r \)-partite graph with \( \binom r 2 \frac{n^2}{r^2} = \qty(1 - \frac{1}{r})\frac{n^2}{2} \) edges.
\begin{theorem}[Tur\'an, form 1]
	Let \( G \) be a graph on \( n \) vertices, and \( \qty(1 - \frac{1}{r}) \frac{n^2}{2} < e(G) \) for \( r \geq 1 \).
	Then \( G \) contains a subgraph of the form \( K_{r+1} \), so it has an \( (r + 1) \)-clique.
\end{theorem}
\begin{proof}
	Suppose that \( G \) has an \( (r + 1) \)-clique.
	For a given \( r \), we prove the result by induction on \( n \), assuming the theorem holds for all lower values of \( r \), then we can complete the proof by induction.

	If \( n \leq r \), the result clearly holds.
	Let \( G \) be a graph that contains no \( (r + 1) \)-clique.
	Suppose \( r \geq 2 \), otherwise the result is trivial.
	Then we can find an \( r \)-clique by induction on \( r \).
	Let \( K \) be such a clique.
	Then each vertex in \( V(G) \setminus K \) have at most \( r - 1 \) neighbours in \( K \), otherwise, this would be an \( (r + 1) \)-clique.
	So
	\[ e(G) \leq \binom r 2 + (r - 1)(n - r) + e(G \setminus K) \leq \binom r 2 + (r - 1)(n - r) + \qty(1 - \frac{1}{r})\frac{(n-1)^2}{2} = \qty(1 - \frac{1}{r}) \frac{n^2}{2} \]
\end{proof}
\begin{remark}
	This is a generalisation of Mantel's theorem.
	If \( r \mid n \), the theorem is sharp by considering the complete \( r \)-partite graph.
\end{remark}
\begin{definition}
	The \emph{Tur\'an graph} \( T_{r,n} \) is the complete \( r \)-partite graph \( K_{n_1, \dots, n_r} \) where \( \sum_{i=1}^r n_i = n \) and \( n_1, \dots, n_r \) differ by at most one.
\end{definition}
\begin{proposition}
	Let \( G \) be a \( r \)-partite graph on \( n \) vertices.
	Then \( e(G) \leq e(T_{r,n}) \).
\end{proposition}
\begin{remark}
	Tur\'an graphs maximise the number of edges among all \( r \)-partite graphs on \( n \) vertices.
\end{remark}
\begin{proof}
	Let \( G \) be an \( r \)-partite graph on \( n \) vertices with the maximum number of edges.
	This graph is complete, since if there is a missing edge, there is a graph with more edges.
	Let \( G = K_{n_1, \dots, n_r} \).
	Suppose that \( n_i - n_j \geq 2 \), so \( G \) is not a Tur\'an graph.
	Then consider the graph obtained by moving an edge from the part with \( n_i \) vertices to the part with \( n_j \) vertices.
	Then we gain a total of \( (n_i - 1) \) edges, and remove \( n_j \) edges.
	But this is at least 1, so we have obtained a graph with more edges.
\end{proof}
\begin{theorem}[Tur\'an, form 2]
	Let \( G \) be a graph on \( n \) vertices and \( r \geq 2 \).
	Then if \( G \) does not contain an \( (r+1) \)-clique, \( e(G) \leq e(T_{r,n}) \).
\end{theorem}
\begin{proof}
	We will transform a graph \( G \) into a complete \( r \)-partite graph without decreasing the number of edges.
	Then, since the Tur\'an graph maximises the amount of edges for such a graph, the result follows.

	Let \( V(G) = \qty{1, \dots, n} \).
	Let \( \alpha_1, \dots, \alpha_r > 0 \) be numbers that are linearly independent over \( \mathbb Q \).
	For \( S \subseteq V(G) \), define \( \mu(S) = \sum_{i \in S} \alpha_i \).

	If \( H \) is a graph on \( n \) vertices, we define the transformation of \( H \), denoted \( T(H) \), as follows.
	Let \( x, y \) be a pair of vertices maximising \( \mu(\qty{x,y}) \) (to break any ties) such that \( N(x) \neq N(y) \) and \( x \not\sim y \), and also either \( \deg x > \deg y \) or both \( \deg x = \deg y \) and \( \mu(N(x)) > \mu(N(y)) \).
	Now define \( T(H) \) to be \( H - y \) along with a new vertex \( x' \) with \( N(x') = N(x) \).

	We first show that if \( H \) does not contain a \( K_{r+1} \), then \( T(H) \) also does not contain a \( K_{r+1} \).
	Suppose that our new graph \( H' \) contains a clique \( K \) isomorphic to \( K_{r+1} \).
	We must have that \( x' \) lies inside this clique, because all other vertices remain the same.
	We know \( x \not\in K \) since \( x\not\sim x' \).
	Then \( K \setminus \qty{x'} \cup \qty{x} \) must be an \( (r+1) \)-clique in \( H \), which is a contradiction.

	Now, consider the sequence \( G, T(G), T(T(G)), \dots \), iteratively applying the transformation \( T \).
	We will now show that this sequence \( (T^{(n)}(G))_n \) eventually stabilises.
	This is because \( e(T(H)) \geq e(H) \), so \( (e(T^{(n)}(G)))_n \) is an increasing sequence of integers which is bounded above by \( \binom n 2 \).
	Note that \( \sum_{1 \leq x \leq n} \mu(N_{T^{(i)}(G)}(x)) \) is also an increasing sequence, but since there are only finitely many possible values for this sum, it must also stabilise.
	Therefore, at some point, the transformation \( T \) will do nothing more to our graph.
	Let \( G_\infty \) be the limiting graph in the sequence \( (T^{(n)}(G))_n \).

	We will show that \( G_\infty \) is a complete \( k \)-partite graph for some \( k \).
	Let \( k = \chi(G_\infty) \), and \( c \) be a \( k \)-colouring of \( G_\infty \).
	We write \( V(G_\infty) = C_1 \cup \dots \cup C_k \) where \( C_i \) is the colour class of vertices with colour \( i \).
	Note that if \( x, y \in C_i \), we have \( x \not\sim y \), so \( N(x) = N(y) \), otherwise the transformation \( T \) would have manipulated the neighbourhoods to be equal.
	Now let \( x \in C_i, y \in C_j \) for \( i \neq j \).
	Suppose \( x \not\sim y \).
	Then \( x' \not\sim y' \) for all other \( x' \in C_i \) and \( y' \in C_j \), so \( C_i \) and \( C_j \) have no edges between them.
	But then by merging \( C_i \) and \( C_j \), we obtain a more optimal colouring, contradicting our assumption that \( k = \chi(G_\infty) \).
	So \( G_\infty \) is a complete \( k \)-partite graph for some \( k \).

	Since \( G_\infty \) does not contain a \( K_{r+1} \), we have \( k \leq r \).
	By the previous proposition, \( e(G_\infty) \leq e(T_{r,n}) \), and \( e(G) \leq e(G_\infty) \) since \( e(H) \leq e(T(H)) \) for all \( H \).
\end{proof}

\subsection{The Zarankiewicz problem}
\begin{definition}
	The \emph{Zarankiewicz number} \( Z(n,t) \) is the maximum number of edges in a bipartite graph \( G = (X \sqcup Y, E) \) with \( \abs{X} = \abs{Y} = n \) such that \( G \) does not contain \( K_{t,t} \).
\end{definition}
\begin{lemma}
	Let \( t \in \mathbb N \), and \( t \geq 2 \).
	Define the function \( f_t(x) = \frac{x(x-1)\dots(x-t+1)}{t!} \).
	Then \( f_t(x) \) is convex for \( x \geq t - 1 \).
\end{lemma}
\begin{proof}
	Let \( s = x - t + 1 \), so \( f_t(x) = \frac{(s+t-1)(s+t-2)\dots s}{t!} \).
	This is a polynomial with nonnegative coefficients.
	Hence it is convex for \( s \geq 0 \), since \( f''(s) \geq 0 \).
\end{proof}
\begin{theorem}
	Let \( t \geq 2 \).
	Then \( Z(n,t) \leq t^{\frac{1}{t}} n^{2 - \frac{1}{t}} + tn \).
\end{theorem}
\begin{remark}
	In particular, as \( n \) increases, \( Z(n,t) \) is eventually lower bounded by \( 2n^{2-\frac{1}{t}} \).
\end{remark}
\begin{proof}
	Note that we may assume that \( \deg y \geq t - 1 \) for all \( y \in Y \).
	If \( \deg y < t - 1 \), we can add an edge and preserve the property that \( G \) contains no \( K_{t,t} \).

	Let \( x_1, \dots, x_t \in X \) be distinct vertices.
	Then \( \abs{N(x_1) \cap \dots \cap N(x_t)} \leq t - 1 \), otherwise we have a \( K_{t,t} \).
	Now, applying Jensen's inequality,
	
	\begin{align*}
		(t-1) \binom n t &\geq \sum_{x_1, \dots, x_t \text{ distinct}} \abs{N(x_1) \cap \dots \cap N(x_t)} \\
		&= \sum_{x_1, \dots, x_t \text{ distinct}} \sum_y \symbb 1_{y \sim x_1} \dots \symbb 1_{y \sim x_t} \\
		&= \sum_y \sum_{x_1, \dots, x_t \text{ distinct}} \symbb 1_{y \sim x_1} \dots \symbb 1_{y \sim x_t} \\
		&= \sum_y \binom{\deg y}{t} \\
		&= n \qty( \frac{1}{n} \sum_y \binom{\deg y}{t} ) \\
		&\geq n \binom{\overline d}{t}
	\end{align*}
	where \( \overline d = \frac{e(G)}{n} \) (since we are in a bipartite graph), using the fact that \( \deg y \geq t - 1 \), so \( x \mapsto \binom x t \) is convex.
	So
	\begin{align*}
		(t-1) \binom n t &\geq n \binom{\overline d}{t} \\
		\frac{tn^t}{t!} &\geq \frac{n(\overline d - t)^t}{t!} \\
		tn^t &\geq n(\overline d - t)^t \\
		t^{\frac{1}{t}} n^{1 - \frac{1}{t}} &\geq \overline d - t \\
		t^{\frac{1}{t}} n^{1 - \frac{1}{t}} &\geq \frac{e(G)}{n} - t \\
		e(G) &\leq t^{\frac{1}{t}} n^{2 - \frac{1}{t}} + tn
	\end{align*}
\end{proof}
\begin{remark}
	If \( t = 2 \), then it is known that \( Z(n,t) \geq cn^{\frac{3}{2}} \) for some contant \( c > 0 \).
	If \( t = 3 \), \( Z(n,t) \geq cn^{\frac{5}{3}} \).
	This is an open problem for \( t = 4 \).
\end{remark}

\subsection{Erd\H{o}s--Stone theorem}
\begin{definition}
	Let \( H \) be a fixed graph, and \( n \in \mathbb N \).
	Then we define the \emph{extremal number} \( \mathrm{ex}(n,H) = \max\qty{e(G) \mid \abs{G} = n, G \text{ contains no copy of } H} \).
\end{definition}
\begin{example}
	\( \mathrm{ex}(n,K_{r+1}) = e(T_{r,n}) \leq \qty(1 - \frac{1}{r})\frac{n^2}{2} \).
	\( \mathrm{ex}(n,P_k) = \frac{n(k-1)}{2} \).
	\( \mathrm{ex}(n,K_{t,t}) \leq 2n^{2-\frac{1}{t}} + tn \).
\end{example}
\begin{theorem}
	Let \( H \) be a fixed nonempty graph.
	Then
	\[ \lim_{n \to \infty} \frac{\mathrm{ex}(n,H)}{\binom n 2} = 1 - \frac{1}{\chi(H) - 1} \]
\end{theorem}
\begin{remark}
	If \( \chi(H) \geq 3 \), this determines the leading order term in the function \( \mathrm{ex}(n,H) \) for large \( n \).
	If \( \chi(H) = 2 \), this theorem implies that \( \frac{\mathrm{ex}(n,H)}{n^2} \to 0 \).
	But in this case, \( H \subseteq K_{t,t} \), and we already know (almost) that \( \mathrm{ex}(n,H) \leq cn^{2-\frac{1}{t}} \), which implies the result from the Erd\H{o}s--Stone theorem.
	It is easy to see that \( \mathrm{ex}(n,H) \geq \qty(1 - \frac{1}{\chi(H) - 1}) \frac{n^2}{2} \), since \( H \) is not contained in any \( T_{(\chi(H)-1),n} \).
\end{remark}
\iffalse
The following proof sketch is non-examinable.

We will consider the case \( \chi(H) = 3 \).
Let \( K_3(t) = T_{3,3t} \) be the complete 3-partite graph with \( t \) vertices in each part.
It suffices to prove the \( \chi(H) = 3 \) case for \( H = K_3(t) \), since each fixed graph \( H \) with \( \chi(H) = 3 \) is contained inside \( K_3(\abs{H}) \).

We prove the following claim.
Let \( \varepsilon > 0 \) and \( t \in \mathbb N \).
Let \( G \) be a graph such that \( \abs{G} = n \) and \( e(G) \geq \qty(\frac{1}{2} + \varepsilon) \frac{n^2}{2} \) where \( n \geq n_0(\varepsilon,t) \).
Then \( G \) contains a copy of \( K_3(t) \).

The following lemma is given without proof.
\begin{lemma}
	Let \( G \) be a graph on \( n \) vertices with average degree at least \( \qty(\frac{1}{2} + \varepsilon)n \), which is equivalent to the condition \( e(G) \geq \qty(\frac{1}{2} + \varepsilon)\frac{n^2}{2} \).
	Then there exists \( \widetilde G \subseteq G \) with \( \delta(\widetilde G) \geq \qty(\frac{1}{2} + \frac{\varepsilon}{2})m \) where \( m = \abs{\widetilde G} \geq \frac{\varepsilon^{\frac 12} n}{8} \).
\end{lemma}

We now prove the main theorem.
Let \( \widetilde G \subseteq G \) be a subgraph with \( \delta(\widetilde G) \geq \qty(\frac{1}{2} + \frac{\varepsilon}{2})m \) where \( m = \abs{\widetilde G} \).
We will find a copy \( K \) of \( K_{s,s} \) in \( \widetilde G \) with \( s = 10 \frac{t}{\varepsilon} \).
Let \( Y = V(\widetilde G) \setminus K \).
Then
\[ e(Y,K) = \sum_{x \in K} \abs{N(x) \cap Y} = \sum_{x \in K} (\deg x - S) \geq \sum_{x \in K} \qty(\frac{1}{2} + \frac{\varepsilon}{4})m = \qty(\frac{1}{2} + \frac{\varepsilon}{4})m\abs{K} \]
Also, \( e(Y,K) = \sum_{y \in Y} \abs{N(y) \cap K} \).
Hence
\[ \qty(\frac{1}{2} + \frac{\varepsilon}{4}) \abs{K} \leq \frac{1}{m} \sum_{y \in Y} \abs{N(y) \cap K} \]
Let \( B = \qty{y \in Y \mid \abs{N(y) \cap K} \geq \frac{1}{2} + \frac{\varepsilon}{8}} \).
We claim \( \abs{B} \geq \frac{\varepsilon m}{8} \).
Suppose this is not true, then
\[ \frac{1}{m}\sum_{y \in Y} \abs{N(y) \cap K} < \frac{1}{m} \frac{\varepsilon m}{8} \abs{K} + \qty(\frac{1}{2} + \frac{\varepsilon}{8})\abs{K} \]
contradicting the previous inequality.
Then we can pick by the pigeonhole principle a vertex on either side of \( K \) connected to some vertex in \( B \), creating a \( K_3 \).
\fi
